package tree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author wujun
 * @date 17-11-23.
 *
 * 本道题我认为是这样的 一颗树加了一条多余的变会造成两种情况： 1. 存在环， 这个可以用并查集来完成 2. 存在某个节点入度为2， 例如1 -> 2, 1 -> 3, 2 -> 3
 */
public class Solution685 {

    public int[] findRedundantDirectedConnection(int[][] edges) {
        int[] union = new int[edges.length + 1];
        Arrays.fill(union, 0);

        List<int[]> handlePairList = new ArrayList<int[]>();
        for (int[] pair : edges) {
            // 命中情况1
            if (hasCircular(union, pair[0], pair[1])) {
                handlePairList.add(pair);
                continue;
            }

            // 命中情况2
            if (!checkInDegree2(union, pair[0], pair[1], handlePairList)) {
                union[pair[1]] = pair[0];
            }
        }

        /* size = 1 */
        if (handlePairList.size() == 1) {
            return handlePairList.get(0);
        }

        List<int[]> sortedPair = new ArrayList<int[]>();
        for (int[] pair : edges) {
            for (int[] pairHandleLast : handlePairList) {
                if (pair[0] == pairHandleLast[0] && pair[1] == pairHandleLast[1]) {
                    sortedPair.add(pair);
                }
            }
        }

        /* size = 2 */
        if (sortedPair.size() == 2) {
            int[] pair0 = sortedPair.get(0);
            int[] pair1 = sortedPair.get(1);

            if (hasCircular(union, pair0[0], pair0[1]) || checkInDegree2(union, pair0[0], pair0[1], handlePairList)) {
                return pair0;
            }

            return pair1;
        }

        /* size = 3 */
        int i = 2;
        int j = 0;
        for (; i > j; i--) {
            int[] unionCopy = new int[edges.length + 1];
            System.arraycopy(union, 0, unionCopy, 0, edges.length + 1);
            for (j = i - 1; j >= 0; j--) {
                if (hasCircular(unionCopy, sortedPair.get(i)[0], sortedPair.get(i)[1])
                        || checkInDegree2(unionCopy, sortedPair.get(i)[0], sortedPair.get(i)[1], handlePairList)) {
                    continue;
                }

                unionCopy[sortedPair.get(i)[1]] = sortedPair.get(i)[0];

                if (hasCircular(unionCopy, sortedPair.get(j)[0], sortedPair.get(j)[1])
                        || checkInDegree2(unionCopy, sortedPair.get(j)[0], sortedPair.get(j)[1], handlePairList)) {
                    continue;
                }

                return sortedPair.get(3 - (i + j));
            }
        }

        return new int[]{0, 0};
    }

    private boolean checkInDegree2(int[] union, int parent, int child, List<int[]> handleLast) {
        if (union[child] != 0) {
            handleLast.add(new int[]{union[child], child});
            handleLast.add(new int[]{parent, child});

            union[child] = 0;

            return true;
        }
        return false;
    }

    private boolean hasCircular(int[] union, int parent, int child) {
        while (parent != 0) {
            parent = union[parent];
            if (parent == child) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
//        int[][] edges = new int[][]{
//                {1, 2},
//                {1, 3},
//                {2, 3}
//        };

//        int[][] edges = new int[][]{
//                {2, 1},
//                {3, 1},
//                {4, 2},
//                {1, 4}
//        };

        int[][] edges = new int[][]{
                {3, 4},
                {4, 1},
                {1, 2},
                {2, 3},
                {5, 1}
        };

        System.out.println(Arrays.toString(new Solution685().findRedundantDirectedConnection(edges)));
    }
}
